COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	begin comment experiments on optimal Boolean evaluation
C00004 00003	table-building procedures insert,add,build_initial_level
C00006 00004	procedure build_shift_tables
C00008 00005	procedure build_next_level
C00010 00006	level←false
C00011 ENDMK
C⊗;
begin comment experiments on optimal Boolean evaluation;
external procedure bail;
define size='177777;
integer ochan,oflg,eof,z,j,k,t,x,m,mt,tz;
integer array ml,mr,spec[0:95];
integer array s[0:size]; comment the sign of s[t] is 1 is truthtable t
is reached in <k steps, the next 19 bits count the number of ways to
	produce truthtable t, and the right 16 bits contain specification
	number t (unrelated to truthtable t);
define msk16='177777,msk20='777777600000,
	msk19='377777600000;
integer array a[0:30]; comment if a[j]≤i<a[j+1] then s[i]land msk16
	specifies a truthtable reached in j steps;
preload_with '377,'7417,'31463,'52525;integer array xt[1:4];
boolean level;  comment are we minimizing levels?;
label loop;
comment table-building procedures insert,add,build_initial_level;

procedure insert(integer t,x);
begin comment insert new specification entry t into s,
	where x explains how this entry was obtained;
s[z]←s[z]+t; z←z+1;
wordout(ochan,t);
wordout(ochan,if level then x else (k lsh 30)+x);
if z>size then go to loop;
end;

procedure add(integer t,a,x);
comment add a to the number of ways of obtaining truthvalue t,
	if t is on the current level;
if s[t]≥0 then
begin if s[t] land msk20=0 then insert(t,x);
if a>'1777777 then a←msk19 else a←a lsh 16;
if (s[t]←s[t]+a)<0 then s[t]←(s[t] land msk16) lor msk19;
end;

procedure build_initial_level;
begin integer i;
add(0,1,0);
if size>'77777 then add('177777,1,0);
for i←1 step 1 until 4 do add(xt[i],1,i);
end;
procedure build_shift_tables;
begin integer procedure p1(reference integer x,y);return(x land y);
integer procedure p2(reference integer x,y);return(x lor y);
integer procedure p3(reference integer x,y);return(x xor y);
integer procedure p4(reference integer x,y);return(x land(lnot y));
integer procedure p5(reference integer x,y);return((lnot x)land y);
integer procedure p6(reference integer x,y);return(lnot x);
integer procedure p7(reference integer x,y);return(y);
integer procedure p8(reference integer x,y);return(lnot(x land y));
procedure buildem(integer procedure p; integer c,flag);
begin integer i,j,ti,tj,tl,tr;
for j←1 step 1 until 4 do if j≤flag then
	begin for i←1 step 1 until 4 do
		begin	tl←tr←0; ti←xt[i]; tj←xt[j];
		if p(0,0) then tl←(lnot ti)land(lnot tj)land msk16;
		if p(0,-1) then tl←tl+((lnot ti)land tj);
		if lnot(p(-1,0)) then tr←ti land(lnot tj);
		if lnot(p(-1,-1))then tr←tr+(ti land tj);
		ml[tz]←tl; mr[tz]←tr; spec[tz]←c+((i lsh 5)+j)lsh 20;
		tz←tz+1;
		end;
	end;
end;
tz←0;
buildem(p8,'1000000,4);
buildem(p7,0,4);
end;
procedure build_next_level;
if level then
begin integer i,j,ti,tj,x,cj,c;
for j←a[k-1] step 1 until a[k]-1 do
	begin tj←s[j] land msk16; cj←(s[tj] land msk19) lsh -16;
	for i←0 step 1 until j do
		begin ti←s[i] land msk16; c←((s[ti] land msk19) lsh -16)*cj;
		x←(ti lsh 20)+tj;
		if x land '400000000000 then x←x xor '400000200000;
		add(lnot(ti lor tj) land msk16,c,x);
		end
	end
end else
begin integer i,j,t,c,tl1,tl2,tl3,tl4,tr1,tr2,tr3,tr4;
for j←a[k-1] step 1 until a[k]-1 do
	begin t←s[j] land msk16; c←(s[t] land msk19) lsh -16;
	tl1←t xor (t lsh 8); tr1←t xor (t lsh -8);
	tl2←t xor (t lsh 4); tr2←t xor (t lsh -4);
	tl3←t xor (t lsh 2); tr3←t xor (t lsh -2);
	tl4←t xor (t lsh 1); tr4←t xor (t lsh -1);
	for i←0 step 4 until tz-4 do
		begin add(t xor(tl1 land ml[i])xor(tr1 land mr[i]),c,t+spec[i]);
		add(t xor(tl2 land ml[i+1])xor(tr2 land mr[i+1]),c,t+spec[i+1]);
		add(t xor(tl3 land ml[i+2])xor(tr3 land mr[i+2]),c,t+spec[i+2]);
		add(t xor(tl4 land ml[i+3])xor(tr4 land mr[i+3]),c,t+spec[i+3]);
		end;
	end;
end;
level←false;
bail;
setformat(10,10);
open(ochan←getchan,"DSK",8,0,2,256,oflg,eof);
enter(ochan,"BOOL.OUT",oflg);
k←0; a[0]←0;  z←0;
build_initial_level;
if not level then build_shift_tables;
loop: while z>a[k] do
	begin comment advance k after printing an extremal example;
	m←10000000; for j←a[k] step 1 until z-1 do
		begin  t←s[j] land msk16; x←s[t] lsh -16;
		if x<m then
			begin m←x; mt←t;
			end;
		s[t]←s[t] lor '400000000000;
		end;
	print(k,z,m,cvos(mt),'15&'12);
	k←k+1; a[k]←z;
	if z≤size then build_next_level;
	end;
wordout(ochan,-1);
close(ochan);
end